{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Peaks and Valleys LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wiggleSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #峰与谷"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个整数数组中，&ldquo;峰&rdquo;是大于或等于相邻整数的元素，相应地，&ldquo;谷&rdquo;是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>[5, 3, 1, 2, 3]\n",
    "<strong>输出:</strong>&nbsp;[5, 1, 3, 2, 3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length &lt;= 10000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [peaks-and-valleys-lcci](https://leetcode.cn/problems/peaks-and-valleys-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [peaks-and-valleys-lcci](https://leetcode.cn/problems/peaks-and-valleys-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i+1]:\n",
    "                    nums[i+1], nums[i] = nums[i], nums[i+1]\n",
    "            else:\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    nums[i+1], nums[i] = nums[i], nums[i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        sort_nums = sorted(nums)\n",
    "        large_index = len(sort_nums) - 1\n",
    "        small_index = 0\n",
    "        index = 0\n",
    "        while index < len(nums):\n",
    "            nums[index] = sort_nums[large_index]\n",
    "            large_index -= 1\n",
    "            index += 1\n",
    "            if index >= len(nums):\n",
    "                break\n",
    "            nums[index] = sort_nums[small_index]\n",
    "            small_index += 1\n",
    "            index += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个\n",
    "            else:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        nums1=sorted(nums)\n",
    "        n=len(nums)\n",
    "        flag=1\n",
    "        for i in range(n):\n",
    "            j=i//2\n",
    "            if flag==1:\n",
    "                nums[i]=nums1[n-1-j]\n",
    "                flag=0\n",
    "            else:\n",
    "                nums[i]=nums1[j]\n",
    "                flag=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        index, lent = 0, len(nums)\n",
    "        if lent<3:return\n",
    "        left=0\n",
    "        right=lent-1\n",
    "        res = nums.copy()\n",
    "        res.sort()\n",
    "        while left<right:\n",
    "            nums[index] = res[right]\n",
    "            index+=1\n",
    "            right-=1\n",
    "            nums[index] = res[left]\n",
    "            index+=1\n",
    "            left+=1\n",
    "        \n",
    "        if (lent%2>0):\n",
    "            nums[index] = res[left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(1, len(nums)):\n",
    "            if i % 2:\n",
    "                if nums[i] > nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "            else:\n",
    "                if nums[i] < nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return []\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i - 1]:\n",
    "                    temp = nums[i]\n",
    "                    nums[i] = nums[i - 1]\n",
    "                    nums[i - 1] = temp\n",
    "            else:\n",
    "                if nums[i] < nums[i - 1]:\n",
    "                    temp = nums[i]\n",
    "                    nums[i] = nums[i - 1]\n",
    "                    nums[i - 1] = temp\n",
    "        \n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return\n",
    "        \n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个\n",
    "            else:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        lastIsFeng = 1\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if lastIsFeng:\n",
    "                if not nums[i] <= nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "            else:\n",
    "                if nums[i] < nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "            lastIsFeng ^= 1\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(0, n, 2):\n",
    "            if i <= n - 2:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \n",
    "        def getMaxIndex(a, b, c):\n",
    "            m = max(nums[a], nums[b], nums[c])\n",
    "            if m == nums[a]: return a\n",
    "            if m == nums[b]: return b\n",
    "            if m == nums[c]: return c\n",
    "\n",
    "        i = 1\n",
    "        while i < len(nums):\n",
    "            maxIdx = getMaxIndex(i-1, i, i+1 if i < len(nums)-1 else i)\n",
    "            if i != maxIdx: nums[i], nums[maxIdx] = nums[maxIdx], nums[i]\n",
    "            i += 2\n",
    "        return nums "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1): \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            else:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if i % 2:\n",
    "                if nums[i] > nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "            else:\n",
    "                if nums[i] < nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0: #谷\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个 -- 关心你大于下一个\n",
    "            else:#峰\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "\n",
    "        # nums.sort()\n",
    "        # n = len(nums)\n",
    "        # for i in range(0, n, 2):\n",
    "        #     if i <= n - 2:\n",
    "        #         nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个\n",
    "            else:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        for i in range(len(nums)-1):\n",
    "\n",
    "            if i %2==0:\n",
    "\n",
    "                if nums[i]>nums[i+1]:\n",
    "                    nums[i],nums[i+1]=nums[i+1],nums[i]\n",
    "                \n",
    "            else:\n",
    "                if nums[i]<nums[i+1]:\n",
    "                    nums[i],nums[i+1]=nums[i+1],nums[i]\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        num1 = nums[:n // 2]\n",
    "        num2 = nums[n // 2:]\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                nums[i] = num2[i//2]\n",
    "            else:\n",
    "                nums[i] = num1[(i-1)//2]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return\n",
    "        is_feng = 0 if nums[0] > nums[1] else 1\n",
    "        for i in range(1, n - 1):\n",
    "            if not is_feng and nums[i] < nums[i + 1]:\n",
    "                pass\n",
    "            elif not is_feng and nums[i] > nums[i + 1]:\n",
    "                nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "            elif is_feng and nums[i] > nums[i + 1]:\n",
    "                pass\n",
    "            elif is_feng and nums[i] < nums[i + 1]:\n",
    "                nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "            is_feng = 1 - is_feng"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        lastIsFeng = False\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if i%2 == 0:\n",
    "                if not nums[i] <= nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "            else:\n",
    "                if nums[i] < nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)-1):\n",
    "            if i%2==0:\n",
    "                if nums[i]<nums[i+1]:\n",
    "                    nums[i],nums[i+1]=nums[i+1],nums[i]\n",
    "            if i%2!=0:\n",
    "                if nums[i]>nums[i+1]:\n",
    "                    nums[i],nums[i+1]=nums[i+1],nums[i]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        nums.sort(reverse = True)\n",
    "        sta = (n+1)//2\n",
    "        for i in range(sta,n):\n",
    "            tmp = nums.pop(i)\n",
    "            nums[(i-sta)*2+1:] = [tmp]+nums[(i-sta)*2+1:]\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while i < n-1:\n",
    "            nums[i],nums[i+1] = nums[i+1],nums[i]\n",
    "            i+=2\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if i % 2:\n",
    "                if nums[i] < nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "            else:\n",
    "                if nums[i] > nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个\n",
    "            else:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        \n",
    "        for i in range(0,n - 1):\n",
    "            if (i % 2 == 0 and nums[i] < nums[i + 1])  or \\\n",
    "            (i % 2 != 0 and nums[i] > nums[i + 1]\n",
    "):\n",
    "                nums[i],nums[i + 1] = nums[i + 1],nums[i]\n",
    "           \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef wiggleSort(self, nums: List[int]) -> None:\n",
    "\t\tcopy = [i for i in nums]\n",
    "\t\tcopy.sort()\n",
    "\t\tleft = 0\n",
    "\t\tright = len(copy) - 1\n",
    "\t\tindex = 0\n",
    "\t\twhile right > left:\n",
    "\t\t\tnums[index] = copy[right]\n",
    "\t\t\tright -= 1\n",
    "\t\t\tindex += 1\n",
    "\t\t\tnums[index] = copy[left]\n",
    "\t\t\tleft += 1\n",
    "\t\t\tindex += 1\n",
    "\t\tif right == left:\n",
    "\t\t\tnums[index] = copy[right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        sorted_nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        nums[0:n:2] = sorted_nums[n // 2:]\n",
    "        nums[1:n:2] = sorted_nums[:n // 2]\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort(reverse=True)\n",
    "        mid_pos = int(len(nums) / 2)\n",
    "        if len(nums) % 2 == 0:\n",
    "            mid_pos += 1\n",
    "        insert_index = 1\n",
    "        for i in range(len(nums) - 1, mid_pos - 1, -1):\n",
    "            n = nums.pop()\n",
    "            nums.insert(insert_index, n)\n",
    "            insert_index += 2\n",
    "        # print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if i % 2:\n",
    "                if nums[i] > nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "            else:\n",
    "                if nums[i] < nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(1, len(nums)): # 峰 谷 峰\n",
    "            if i % 2 == 1:\n",
    "                if nums[i] > nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "                else:\n",
    "                    pass\n",
    "            else:\n",
    "                if nums[i] > nums[i-1]:\n",
    "                    pass\n",
    "                else:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] >= nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "            else:\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)-1):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "            else:\n",
    "                if nums[i] > nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        nums.sort()\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if i % 2 == 0:\n",
    "                tmp = nums[i]\n",
    "                nums[i] = nums[i - 1]\n",
    "                nums[i - 1] = tmp\n",
    "                \n",
    "if __name__ == \"__main__\":\n",
    "    solution = Solution()\n",
    "    nums = [5, 1, 3, 2, 3]\n",
    "    solution.wiggleSort(nums)\n",
    "    print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个\n",
    "            else:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(0, n, 2):\n",
    "            if i <= n - 2:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        sorted_nums = sorted(nums)\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "\n",
    "        i1 = 0\n",
    "        i2 = 1\n",
    "        while left <= right:\n",
    "            nums[i1] = sorted_nums[left]\n",
    "            if i2 < len(nums):\n",
    "                nums[i2] = sorted_nums[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "            i1 += 2\n",
    "            i2 += 2\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(1, len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] < nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "            else :\n",
    "                if nums[i] > nums[i - 1]:\n",
    "                    nums[i], nums[i - 1] = nums[i - 1], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        _nums = sorted(nums, reverse=True)\n",
    "        i, j = 0, len(nums)-1\n",
    "        n = 1\n",
    "        for k in range(len(nums)):\n",
    "            if n % 2 == 1:\n",
    "                nums[k] = _nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                nums[k] = _nums[j]\n",
    "                j -= 1\n",
    "            n += 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(0,n-1,2):\n",
    "            nums[i],nums[i+1] = nums[i+1],nums[i]\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        s=sorted(nums)\n",
    "        lenth=len(nums)\n",
    "        nums1=[]\n",
    "        nums2=[]\n",
    "        n=0\n",
    "        for i in s:\n",
    "            if n>=(lenth+1)//2:\n",
    "                break\n",
    "            nums1.append(i)\n",
    "            n+=1\n",
    "        n=0\n",
    "        for i in s:\n",
    "            if n>=(lenth+1)//2:\n",
    "                nums2.append(i)\n",
    "            n+=1\n",
    "        n=0\n",
    "        i=0\n",
    "        j=0\n",
    "        while n<lenth:\n",
    "            if n%2==0:\n",
    "                nums[n]=nums1[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                if lenth%2!=0:\n",
    "                    if j==lenth//2:\n",
    "                        break\n",
    "                nums[n]=nums2[j]\n",
    "                j+=1\n",
    "            n+=1\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        A=sorted(nums)\n",
    "        n=len(nums)\n",
    "        p=0\n",
    "        for i in range(n):\n",
    "            if i&1==0:\n",
    "                nums[i]=A[p]\n",
    "            else:\n",
    "                nums[i]=A[n-1-p]\n",
    "                p+=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[3,5,2,1,6,4]\n",
    "[5, 3, 1, 2, 3]\n",
    "[]\n",
    "\n",
    "nums.length <= 10000\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        if not nums: return\n",
    "        for i in range(1, len(nums)):\n",
    "            if i % 2:\n",
    "                if nums[i-1] > nums[i]: nums[i-1], nums[i] = nums[i], nums[i-1]\n",
    "            else:\n",
    "                if nums[i-1] < nums[i]: nums[i-1], nums[i] = nums[i], nums[i-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        for i in range(0,n,2):\n",
    "            if i<=n-2:\n",
    "                nums[i],nums[i+1]=nums[i+1],nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(1, n, 2):\n",
    "            nums[i-1], nums[i] = nums[i], nums[i-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            if i % 2 == 1:\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "            else:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)-1):\n",
    "            if(i % 2):\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "            else:\n",
    "                if nums[i] > nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "        return \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)-1):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "            else:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "        return nums\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个\n",
    "            else:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        self.qSort(nums, 0, len(nums)-1)\n",
    "        \n",
    "        for i in range(0, len(nums), 2): \n",
    "            if i+1 <= len(nums)-1:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "    \n",
    "    def qSort(self, arr, l, r):\n",
    "        if l >= r:\n",
    "            return \n",
    "        \n",
    "        piv_idx = random.randint(l, r)\n",
    "        piv = arr[piv_idx]\n",
    "\n",
    "        arr[l], arr[piv_idx] = arr[piv_idx], arr[l]\n",
    "\n",
    "        i = l+1\n",
    "        j = l \n",
    "        k = r+1\n",
    "        while i<k:\n",
    "            if arr[i] < piv:\n",
    "                arr[i], arr[j+1] = arr[j+1], arr[i]\n",
    "                i+=1\n",
    "                j+=1\n",
    "            elif arr[i] > piv:\n",
    "                arr[i], arr[k-1] = arr[k-1], arr[i]\n",
    "                k-=1\n",
    "            else:\n",
    "                i+=1\n",
    "        \n",
    "        arr[l], arr[j] = arr[j], arr[l]\n",
    "        self.qSort(arr, l, j-1)\n",
    "        self.qSort(arr, k, r)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(1, len(nums)):\n",
    "            if i%2==0:\n",
    "                if nums[i]<nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "            else:\n",
    "                if nums[i]>nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        l, r = 0, n-1\n",
    "        for i in range(0, n - 1, 2):\n",
    "            nums[i], nums[i+1] = nums[i+1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \"\"\"方法一、贪心法\"\"\"\n",
    "        # 先确定数组最后的形式: 谷-峰-谷(0-1-2)\n",
    "        # 偶数位是谷，奇数位是峰\n",
    "        for i in range(len(nums)-1):  # 这里需要 -1，防止索引溢出\n",
    "            if i % 2 == 0:  # 偶数位 是谷，数值要比后一位的奇数位要小\n",
    "                if nums[i] > nums[i+1]:  # 如果 偶数位 数值比后一位的奇数位 大\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]  # 交换当前位置与后一个位置的数字\n",
    "            else:  # 奇数位 是峰，数值要比后一位的偶数位要大\n",
    "                if nums[i] < nums[i+1]:  # 如果 奇数位 数值比后一位的偶数位 小\n",
    "                    nums[i], nums[i+1] = nums[i+1], nums[i]  # 交换当前位置与后一个位置的数字"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        tmp = sorted(nums)\n",
    "        for i in range((len(nums)-1)//2+1):\n",
    "            nums[2*i] = tmp[i]\n",
    "            if len(nums)-1-i>i:\n",
    "                nums[2*i+1] = tmp[len(nums)-1-i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        if len(nums) <= 2:\n",
    "            return None\n",
    "\n",
    "        if nums[0] >= nums[1]:\n",
    "            flag = True\n",
    "        else:\n",
    "            flag = False\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            if flag:\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    temp = nums[i]\n",
    "                    nums[i] = nums[i+1]\n",
    "                    nums[i+1] = temp\n",
    "                pass\n",
    "            else:\n",
    "                if nums[i] > nums[i+1]:\n",
    "                    temp = nums[i+1]\n",
    "                    nums[i+1] = nums[i]\n",
    "                    nums[i] = temp\n",
    "\n",
    "            flag = not flag\n",
    "\n",
    "        return None\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort(reverse = True)\n",
    "        n = len(nums)\n",
    "        if n%2 == 0:\n",
    "            right = n-2\n",
    "        else:\n",
    "            right = n-1\n",
    "        left = 1\n",
    "        while left < right:\n",
    "            nums[left],nums[right] = nums[right], nums[left]\n",
    "            left += 2\n",
    "            right -= 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        nums.sort(reverse = True)\n",
    "        sta = (n+1)//2\n",
    "        for i in range(sta,n):\n",
    "            nums[(i-sta)*2+1:] = [nums[i]]+nums[(i-sta)*2+1:i]+nums[i+1:]\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        for i in range(0, len(nums), 2): \n",
    "            if i+1 <= len(nums)-1:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        self.qSort(nums, 0, len(nums)-1)\n",
    "        \n",
    "        for i in range(0, len(nums), 2): \n",
    "            if i+1 <= len(nums)-1:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "    \n",
    "    def qSort(self, arr, l, r):\n",
    "        if l >= r:\n",
    "            return \n",
    "        \n",
    "        piv_idx = random.randint(l, r)\n",
    "        piv = arr[piv_idx]\n",
    "\n",
    "        arr[l], arr[piv_idx] = arr[piv_idx], arr[l]\n",
    "\n",
    "        i = l+1\n",
    "        j = l \n",
    "        k = r+1\n",
    "        while i<k:\n",
    "            if arr[i] < piv:\n",
    "                arr[i], arr[j+1] = arr[j+1], arr[i]\n",
    "                i+=1\n",
    "                j+=1\n",
    "            elif arr[i] > piv:\n",
    "                arr[i], arr[k-1] = arr[k-1], arr[i]\n",
    "                k-=1\n",
    "            else:\n",
    "                i+=1\n",
    "        \n",
    "        arr[l], arr[j] = arr[j], arr[l]\n",
    "        self.qSort(arr, l, j-1)\n",
    "        self.qSort(arr, k, r)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        sorted_nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        nums1 = sorted_nums[n // 2:]\n",
    "        nums2 = sorted_nums[:n // 2]\n",
    "        for i in range(0, n, 2):\n",
    "            if nums1:\n",
    "                nums[i] = nums1.pop()\n",
    "            if nums2:\n",
    "                nums[i + 1] = nums2.pop() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        \n",
    "        for i in range(1, len(nums) - 1, 2):\n",
    "            nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "\n",
    "# 示例\n",
    "# nums = [5, 8, 4, 2, 3, 4, 6]\n",
    "# sol = Solution()\n",
    "# sol.wiggleSort(nums)\n",
    "# 输出：nums = [2, 4, 3, 5, 4, 6, 8] 或者其他有效的峰谷交替数组\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "\n",
    "        8 1 7 2 6 3 5 4\n",
    "        8 7 6 5 1 2 3 4\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(0, n - 1, 2):\n",
    "            nums[i], nums[i + 1] = nums[i + 1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(1, len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] < nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "            else:\n",
    "                if nums[i] > nums[i-1]:\n",
    "                    nums[i], nums[i-1] = nums[i-1], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            # 偶数个 \n",
    "            if i % 2 == 0:\n",
    "                if nums[i] > nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]           \n",
    "            # 奇数个\n",
    "            else:\n",
    "                if nums[i] < nums[i + 1]:\n",
    "                    nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        flag = True\n",
    "        for i in range(len(nums)-1):\n",
    "            if flag:\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    nums[i],nums[i+1] = nums[i+1],nums[i]\n",
    "                flag = False\n",
    "            else:\n",
    "                if nums[i] > nums[i+1]:\n",
    "                    nums[i],nums[i+1] = nums[i+1],nums[i]\n",
    "                flag = True\n",
    "                 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        nums.sort(reverse = True)\n",
    "        sta = (n+1)//2\n",
    "        for i in range(sta,n):\n",
    "            nums[(i-sta)*2+1:] = [nums[i]]+nums[(i-sta)*2+1:i]+nums[i+1:]\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        n = len(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        nums1 = nums.copy()\n",
    "        for i in range(0, n, 2):\n",
    "            nums[i] = nums1[i//2]\n",
    "        for i in range(1, n, 2):\n",
    "            nums[i] = nums1[n-1-i//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums) - 1):\n",
    "            if ~i & 1 and nums[i] < nums[i + 1] or i & 1 and nums[i] > nums[i + 1]:\n",
    "                nums[i], nums[i + 1] = nums[i + 1], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        nums.sort(reverse = True)\n",
    "        sta = (n+1)//2\n",
    "        for i in range(sta,n):\n",
    "            nums[(i-sta)*2+1:] = [nums[i]]+nums[(i-sta)*2+1:i]+nums[i+1:]\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        for i in range(0, len(nums), 2): \n",
    "            if i+1 <= len(nums)-1:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        lst=[]\n",
    "        a=nums[:len(nums)//2]\n",
    "        b=nums[(len(nums)//2):]\n",
    "        for i in range(0,len(a)):\n",
    "            lst.append(b[-i-1])\n",
    "            lst.append(a[-i-1])\n",
    "        if len(nums)%2==1:\n",
    "            lst.append(b[0])\n",
    "        for i in range(len(lst)):\n",
    "            nums[i]=lst[i]\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        for i in range(0, len(nums), 2): \n",
    "            if i+1 <= len(nums)-1:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(0, n, 2):\n",
    "            if i <= n - 2:\n",
    "                nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "\n",
    "\n",
    "# 先排序，再依次遍历数组，每两个数交换位置。\n",
    "# 也可以不排序，直接判断奇数位和偶数位的数字是否符合要求。\n",
    "\n",
    "# 作者：木子\n",
    "# 链接：https://leetcode.cn/problems/peaks-and-valleys-lcci/solutions/1160746/python-mian-shi-ti-1011-feng-yu-gu-by-li-hiu0/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
